package com.vilynn.learning.special;

import com.alibaba.fastjson.JSON;

/**
 * Created by wangweilin on 2018/11/2.
 */
public class SortMain {

    public static void main(String[] args) {
        int[] arr = new int[]{1,255,6,21,2,-1,-333,4};
        System.out.println(JSON.toJSONString(arr));
        long start = System.nanoTime();
//        bubbleSort(arr);
//        selectSort(arr);
//        insertSort(arr);
//        quickSort(arr);
        shellSort(arr);
        long end = System.nanoTime();
        System.out.println("花费时间ns：" + (end - start));
        System.out.println(JSON.toJSONString(arr));
    }

    private static void shellSort(int[] arr) {
        selectSort(arr, arr.length/2+1);
    }

    private static void selectSort(int[] arr, int h) {
        while (h > 0){

        }
    }

    static void quickSort(int a[],int left,int right)
    {
        int i=left;
        int j=right;
        int temp=a[left];
        if(left>=right)
            return;
        while(i!=j)
        {
            while(i<j&&a[j]>=temp){
                j--;
            }
            if(j>i) {
                a[i] = a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位
            }
            while(i<j&&a[i]<=temp) {
                i++;
            }
            if(i<j) {
                a[j] = a[i];
            }
        }
        a[i]=temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
        quickSort(a,left,i-1);/*递归左边*/
        quickSort(a,i+1,right);/*递归右边*/
    }

    private static void quickSort(int[] arr) {
//        quickSort(arr, 0, arr.length-1);
        quickSortMy(arr, 0, arr.length-1);
    }

    private static void quickSortMy(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        int base = arr[left];
        while (i != j) {
            while (right > left) {
                if(arr[right] > base){
                    arr[left] = arr[right];
                    break;
                }
                if(--right == left){
                    break;
                }
            }
            while (right > left) {
                if(arr[left] < base){
                    arr[right] = arr[left];
                    break;
                }
                if(++left == right){
                    break;
                }
            }
            if(left == right){
                arr[left] = base;
                break;
            }
        }
        if(i < right){
            quickSortMy(arr, i, right-1);
        }
        if(right < j){
            quickSortMy(arr, right+1, j);
        }
    }

    private static void insertSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int j = i;
            do{
                if(j > 0 && arr[j] > arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                j--;
            }while (j > 0 && arr[j] > arr[j+1]);
        }
    }

    private static void selectSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int maxIndex = i;
            for (int j = i+1; j < len; j++) {
                if(arr[j] > arr[maxIndex]){
                    maxIndex = j;
                }
            }
            if(maxIndex > i){
                int temp = arr[i];
                arr[i] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
        }
    }

    private static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if(arr[j] > arr[i]){
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    }
}
